Spargere in intervale de puteri ale lui doi. Astfel toate operatiile se fac in lg(N). Unde N e marimea vectorului.

Code:

#include <fstream>
using namespace std;

ifstream F("Aib.in");
ofstream G("Aib.out");

#define zeros(i) ( ( i^(i-1) ) & i )
#define Dmax 1011

int x,y,N,M;
int AIB[Dmax];

void Add(int x, int quantity)
{
    int i;

    for (i = x; i <= N; i += zeros(i))
        AIB[i] += quantity;
}

int Compute(int x)
{
    int i, ret = 0;

    for (i = x; i > 0; i -= zeros(i))
        ret += AIB[i];
    return ret;
}

int main()
{
	for (int i=1;i<=M;++i)
	{
		F>>x;
		if ( x==1 )
		{
			F>>x>>y;
			Add(x,y);
			continue;
		}
		if ( x==2 )
		{
			F>>x>>y;
			Add(x,-y);
			continue;
		}
		if ( x==3 )
		{
			F>>x>>y;
			G<<Compute(y)-Compute(x-1)<<'\n';
			continue;
		}
	}
}
